1. Field of the Invention
The present invention relates to the field of election auditing.
2. Brief Description of the Related Art
Security analyses of computerized voting systems, including DREs and optical scan machines, have exposed numerous vulnerabilities that could compromise the integrity of elections performed using these devices. See Kohno, T., Stubblefield, A., Rubin, A., and Wallach, D., “Analysis of an electronic voting system,” Proc. 2004 IEEE Symposium on Security and Privacy, pp. 27-42; Feldman, A., Halderman, J. A., and Felten, E., “Security analysis of the Diebold AccuvoteTS voting machine,” Proc. 2007 USENIX/ACCURATE Electronic Voting Technology Workshop (EVT '07). One proposed defense against such attacks is to produce voter-verified paper records and audit them to ensure that they support the totals claimed by the machines.
The most common auditing method is the precinct-based audit, in which workers count all paper ballots from selected precincts and compare the results to the reported precinct tallies. See Appel, A. W., “Effective audit policy for voter verified paper ballots in New Jersey,” February 2007; Rivest, R. L., “On estimating the size of a statistical audit,” November 2006; Rivest, R. L., “On auditing elections when precincts have different sizes,” April 2007; Saltman, R. G., “Effective use of computing technology in vote tallying,” Tech. Rep. NBSIR 75687, National Bureau of Standards, March 1975. Unfortunately, performing precinct-based audits can require considerable time, labor, and expense. These costs are multiplied by the complexity of the ballots in many elections, which may include dozens of contests. In a trial recount of a DRE paper trail performed in Cobb County, Ga., workers took an average of 5 minutes per ballot to audit 976 votes at a total cost of nearly $3,000. Dunn, S., “Voter verifiable paper audit trail pilot project,” Cobb County, Georgia, November 2006. Unless efficiency can be improved, performing a similar recount of 3% of precincts in New Jersey could cost more than $200,000. Slow, expensive manual recounts limit the level of confidence that can be achieved within a fixed election budget, and they may delay the detection of errors until well after election results have been announced and losing candidates have conceded.
Statistical “ballot-based” audits are an alternative to manually recounting every ballot from selected precincts. Workers sample from all the paper ballots in all precincts and use the sample to assess the accuracy of the original count. Ballot-based audits tend to be more efficient than traditional precinct-based audits, since fewer ballots need to be recounted to achieve the same level of confidence in the result. Neff, C. A., “Election confidence: A comparison of methodologies and their relative effectiveness at achieving it,” December 2003. For example, in a statewide race in New Jersey, fewer than one ballot per precinct (4,599 ballots total) would need to be sampled to achieve 99% confidence that the outcome had not been shifted by more than 0.2%. By contrast, over 150,000 ballots (6.9% of precincts) would need to be recounted using standard precinct-based audits (e.g., Stanislevic, H., “Random auditing of voting systems: How much is enough?,” August 2006) to achieve the same confidence.
Neff and Johnson were among the first to propose combining ballot-based audit techniques with electronic voting. See Johnson, K. C., “Election certification by statistical audit of voter verified paper ballots,” October 2004. Neff assumes that the voting machines link each paper ballot to its electronic counterpart using, for example, a unique identifier printed on the paper ballot and stored with the electronic ballot. When voting is complete, each precinct commits to its set of electronic ballots, then demonstrates that the paper ballots in a given random sample match the corresponding electronic ballots.
The primary weakness of this method is that it establishes the link between electronic and paper ballots at the time that votes are cast. This raises problematic voter privacy issues. For example, if the ballots are linked using sequentially increasing serial numbers, observers could correlate votes with the order in which they were cast, which can reveal the identity of voters. While a cryptographic link might protect privacy, opaque, random-looking identifiers printed on ballots may provide covert channels for leaking voter identities. Even if used securely, they might aid malicious parties who seek to intimidate voters by undermining their confidence in the secrecy of the ballot. Our audit strategy postpones linking paper and electronic records until the recount phase, which allows it to achieve equivalent confidence without jeopardizing privacy or resorting to cryptography.
Johnson alternatively proposes delaying both vote tallying and serial number printing until after all ballots are submitted, allowing voting machines to be simple, memory-less ballot printers. Voters submit their ballots, which, once polls close, are randomized and scanned/tallied. The tallying machine is therefore able to print serial numbers while scanning without privacy risk. Unlike Johnson, we assume that the voting machines maintain an electronic tally, which helps deter traditional attacks against paper-based voting, such as ballot-box stuffing, and, as we will show, provides opportunities for improving the efficiency of the audit.